{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "fe04379d",
   "metadata": {},
   "source": [
    "可以在[Bookshop.org](https://bookshop.org/a/98697/9781098155438) 和\n",
    "[Amazon](https://www.amazon.com/_/dp/1098155432?smid=ATVPDKIKX0DER&_encoding=UTF8&tag=oreilly20-20&_encoding=UTF8&tag=greenteapre01-20&linkCode=ur2&linkId=e2a529f94920295d27ec8a06e757dc7c&camp=1789&creative=9325)获取纸制版和电子版的*Think Python 3e*."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "e55de5cd",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "from os.path import basename, exists\n",
    "\n",
    "def download(url):\n",
    "    filename = basename(url)\n",
    "    if not exists(filename):\n",
    "        from urllib.request import urlretrieve\n",
    "\n",
    "        local, _ = urlretrieve(url, filename)\n",
    "        print(\"Downloaded \" + str(local))\n",
    "    return filename\n",
    "\n",
    "download('https://gitee.com/regentsai/Think_Python_3e_CN/blob/master/thinkpython.py');\n",
    "download('https://gitee.com/regentsai/Think_Python_3e_CN/blob/master/diagram.py');\n",
    "\n",
    "import thinkpython"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "737e79eb",
   "metadata": {},
   "source": [
    "# 第10章：字典\n",
    "\n",
    "本章展示Python内建的类型：字典。它是Python最好的功能之一，也是许多高效和优雅算法的组成部分。\n",
    "\n",
    "我们将使用字典计算一本书中的唯一单词数量以及每个单词出现的次数。在练习中，我们将使用字典解决字谜。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "be7467bb",
   "metadata": {},
   "source": [
    "## 字典是一种映射\n",
    "\n",
    "**字典dictionary**有点像列表，但更加通用。在列表中，索引必须是整数；在字典里索引可以是（几乎）任何类型。例如，假设我们有一个数字单词的列表："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "20dd9f32",
   "metadata": {},
   "outputs": [],
   "source": [
    "lst = ['zero', 'one', 'two']"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "aa626f88",
   "metadata": {},
   "source": [
    "我们可以使用整数作为索引，获得对应的单词。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "9b6625c0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'one'"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lst[1]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c38e143b",
   "metadata": {},
   "source": [
    "但是假设我们想要换一个方向，通过单词来获得对应的整数。我们无法直接对列表这样操作，但我们可以用字典来获得。我们将创建一个空的字典，赋值给`numbers`变量。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "138952d9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{}"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "numbers = {}\n",
    "numbers"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3acce992",
   "metadata": {},
   "source": [
    "花括号`{}`表示一个空字典。要向字典中添加元素,我们将使用方括号。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "007ef505",
   "metadata": {},
   "outputs": [],
   "source": [
    "numbers['zero'] = 0"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1dbe12c3",
   "metadata": {},
   "source": [
    "这个赋值语句为字典添加一个**项item**，这个项表示一个**键key**和一个**值value**之间的联系。在这个例子中，键是字符串`'zero'`，值是整数`0`。如果我们显示该字典，我们看到它包含一个项，项包含一个键和一个值，键和值之间用冒号`:`分隔。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "753a8fbc",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'zero': 0}"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "numbers"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ad32c23d",
   "metadata": {},
   "source": [
    "我们可以继续添加更多项。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "835aac1e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'zero': 0, 'one': 1, 'two': 2}"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "numbers['one'] = 1\n",
    "numbers['two'] = 2\n",
    "numbers"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "278901e5",
   "metadata": {},
   "source": [
    "现在字典包含3个项。要查找一个键，获得对应的值，我们使用方括号运算符。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "c0475cee",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "numbers['two']"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "df5724e6",
   "metadata": {},
   "source": [
    "如果键不在字典中，将得到`KeyError`错误。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "30c37eef",
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "ename": "KeyError",
     "evalue": "'three'",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31mKeyError\u001b[0m\u001b[0;31m:\u001b[0m 'three'\n"
     ]
    }
   ],
   "source": [
    "%%expect KeyError\n",
    "numbers['three']"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2a027a6b",
   "metadata": {},
   "source": [
    "`len`函数对字典有效，它将返回字典的项数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "1b4ea0c2",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(numbers)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "58221e96",
   "metadata": {},
   "source": [
    "在数学语言中，字典表示的是一个从键到值的**映射mapping**，你可以说每个键“映射到”一个值。在这个例子中，每个单词映射到对应的整数。\n",
    "\n",
    "以下图像显示了`numbers`的状态图。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "eba36a24",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "from diagram import make_dict, Binding, Value\n",
    "\n",
    "d1 = make_dict(numbers, dy=-0.3, offsetx=0.37)\n",
    "binding1 = Binding(Value('numbers'), d1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "9016bf4b",
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAMsAAACQCAYAAACmsp8HAAAAOnRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjEwLjAsIGh0dHBzOi8vbWF0cGxvdGxpYi5vcmcvlHJYcgAAAAlwSFlzAAAPYQAAD2EBqD+naQAADU5JREFUeJzt3XlQ1PUfx/HnCsIKwlgeeXCJBha4IBq0oAhomeORTpk65FVNWU1Kh5Y29oddOjFNoQY5mI2WZzYR5YTNKJAEmHiQpqIilIYO6JiY4rm/Pxr355H2gVYBez1mHGeX736/n133ufvFYd9YHA6HAxH5Ry0aewEizYViETGkWEQMKRYRQ4pFxJBiETGkWEQMKRYRQ4pFxJBiETGkWEQMKRYRQ4pFxJBiETGkWEQMKRYRQ4pFxJBiETGkWEQMKRYRQ4pFxJBiaaIsFgsnT54kMjKS06dP33DbTz/9lLKyslu0sv8uxdLEbdu2jVatWt1wG8VyayiWJuLLL7+kR48e2O123nzzTef1l95hAHbt2sWgQYOw2WzYbDYyMjLIzMxk8+bNTJkyhcjISNauXdtYd+H255BGd+TIEcedd97p2L17t8PhcDjmzp3rABy1tbXOv8+dO+e4++67HStXrnTerrq62uFwOBz9+/d3ZGdnN8ra/0v0ztIEFBUVERUVRWhoKABPP/30Ndvs2bOH8+fP89hjjzmva9eu3S1bo+g0rElwaIJus6BYmgC73c7WrVud36RnZmZes01oaCgeHh6sXr3aeV1NTQ0Avr6+/PHHH7dmsf9hiqUJ6NChAwsXLmTYsGHExsbSosW1/yzu7u5kZWWxcOFCevbsic1mY82aNcBfp22zZ8/WN/g3mcWhcwARI3pnETGkWEQMKRYRQ+6NvYD/utra2sZewn+ej4+P0XZ6ZxExpFhEDCkWEUOKRcSQYhExpFhEDCkWEUOKRcSQYhEx1ORiufwz53Kl8PDw2+o4rrRv3z4GDhxIr169SEhIYPfu3S4/RpOLxRXOnz/f2Eto0m7HxyclJYVJkyaxdetWUlJSeP75511+jHrFYrFYmDt3LjExMXTt2pXFixc7vxYUFMSOHTucl/v06UNubi4ACQkJTJs2jfj4ePz9/XnvvfdYsWIFsbGxBAYGsmLFiiuOk5qaSlxcHCEhISxfvtx5/U8//URSUhJ9+vQhKirK+eGniooK2rVrx+zZs+nXrx/z5s0jOzsbm81GZGQk4eHhZGVl1fvBcZU///yTjz/+mPz8fOrq6hq8n7Zt21JaWkpcXJzzT5cuXXj33XcBKCkpYejQofTv359+/fo573NlZSVBQUHMmTOHQYMGkZGRwf79+xk+fDh2u524uDi++eabK47T2E6dOsXSpUspKirizJkzN9y2urqa7du3M3r0aAAefvhhKisrqaysdOma6v2DlFarleLiYnbt2kV0dDTjxo3D3f2fd/Prr7+Sm5vL4cOH6datGy+//DI//vgjmzZtYsSIEYwZM8a5rcVioaCggPLycqKjo+nbty8+Pj4888wzfPvtt3Tq1Imamhp69+5NXFwcAEePHqV79+688cYbAERERJCRkUFsbCwXL17kxIkT9b2rLtOqVSuCgoLIz8+nsLAQu91OdHQ0Vqu1XvvJy8sDoKCgAID8/HxeeOEFJkyYwPHjx0lJSWH16tV07NiRo0ePEh8fz/333w/AsWPHCA4O5rXXXgMgMTGR8ePHM2nSJPbt28eAAQOIjIzEz8/PeZzGZLVa8ff3p7i4mJKSEnr37k2vXr3w9PS8ZtuDBw/SsWNH5/PQYrHg5+fHwYMHCQwMdNma6h1LcnIyAPfccw/u7u4cPnwYPz+/f7zdqFGjaNGiBZ07d6Zdu3aMGDECgN69e1NVVUVdXZ3zyfPUU08BEBwcTN++ffnhhx9o06YN5eXlDB482LlPh8PBnj17CAwMxGq1MnbsWOfXBgwYQEpKCo8++igPPvggkZGR16yprKyMkpKS+j4EDRYYGMixY8fIzc0lLy+PpKQkbDZbg/a1a9cunnvuOVatWkXnzp3JycmhoqKCRx55xLmNw+Fg7969+Pv7Y7VaGTVqFPDXTzr//PPPjB8/HoDu3btjt9spLCx0bnM95eXllJaWNmjNDdGlSxeOHz9OYWEhRUVFxMbGEh0dfc12Fovliss34wPADXpnucTNzc15/uvu7s6FCxecX7v6dOPq21267ObmBtz4PNpiseBwOLDZbOTn51/z9YqKCry9va94wN5//3127tzJhg0bmDBhAsnJyUyfPr0+d9XlXPUPWFVVxZgxY1iwYAH33nuvc99hYWF8991312xfWVmJl5eX8/G5tI6rn2BXX24u/Pz8+P333zl//jzu7u44HA4OHTpk9CJeHy77PEu3bt0oLi4mIiKCTZs2sWfPngbv65NPPmHWrFlUVFSwceNG5s2bR+vWrdm7dy/r168nKSkJ+Gu06aUny9V2795NWFgYYWFhuLu7s27dumu2CQkJISQkpMHrNHXx4kXWrVvH5s2badmyJQkJCc7TsPp+nqW2tpZRo0Yxc+ZM+vfv77w+JiaG/fv3k5eX57y+tLSUHj16XLMPX19fevbsybJly3j88ccpLy+nqKiI1NTUfzx+cHAwwcHB9VpzQ1y8eJH8/Hy2b9+Ou7s7drv9uqdh7du3x2azsXLlSpKTk8nKyiIgIMClp2DgwljefvttJkyYwKJFi4iKiiIsLKzB+/L09CQuLo7q6mrmzZuHv78/ANnZ2UybNo0XX3yRc+fOERAQwFdfffW3+5gxYwZlZWV4eHjg5eVFenp6g9fzb50+fZrKykri4+Mb9L3K5b7++mvKyspIS0sjLS0NgCeeeIInn3ySlStXMmvWLGbMmMG5c+fw8/O74j9ILpeZmUlKSgofffQRFouF+fPnu/yV+N+oq6vjt99+IyYm5rqRXO7DDz9k8uTJpKam4uvrS0ZGhsvXpOkujUyflGx8+qSkiIspFhFDikXEkGIRMaRYRAwpFhFDikXEkGIRMaRYRAwpFhFDikXEkGIRMaRYRAwpFhFDikXEkGIRMaRYRAwpFhFDikXEkGIRMaRYRAwplmbqZk66b25T9KdNm0Z4eDi+vr788ssvN+04ikWavREjRpCTk0NAQMBNPY5iaaYuTbrfsmULAwYMwG63k5CQQFFREfD/yflvvfUW8fHxREREkJOT47z99SbuX77vxlSfKfqXfpvAzaYhe43s3wzZO3v2LJGRkaSlpTFw4EAKCwsZP34827Zto6amhp49e7J8+XKGDBnC999/z6uvvsqWLVs4fvw4w4YNu2bi/vr167nrrrtceO8a7urxrTeaon9JeHg4q1atuu5I3+sxHbLnsvGtcuvt3buXli1bMnDgQADsdjvt27dnx44ddOzYEW9vb4YMGQJAdHQ0Bw4cAKC4uPi6E/f/KZamOkX/VlAszZjD4fjbyfeXrrv8VdjNzc35Ww5uNHFfrk+xNGMhISGcPXvWOTm/uLiY6upqwsLCqKmpue7tbjRx38PD44bHbIpT9G8VxdKMeXh4sHTpUqZPn86pU6fw9PRkyZIleHt73zCWO+64o14T9xtDfabov/TSS6xdu5YjR44wfPhwvL292b59u8vXpG/wG5mm6Dc+TdEXcTHFImJIsYgYUiwihhSLiCHFImJIsYgYUiwihhSLiCHFImJIsYgYUiwihhSLiCHFImJIsYgYUiwihhSLiCHFImJIsYgYUiwihhSLiCHF0oxdmna/YMECqqurXbbfd955h88//9xl+7vZ6urqGDt2LL169SIuLo6RI0dSWVnp8uMolttAenq6S2NpjiZOnMiWLVsoKCjgoYceYsqUKS4/hmJpxtq2bcucOXOoqqpi3LhxxMXFUVpaSmhoKFVVVQAkJyfzwAMPAHD69GkCAgI4c+YMFy5c4PXXXycmJoaYmBheeeUVzp49C0Dr1q2xWq2Ndr+gflP0rVYrgwYNco6tve+++6ioqHD5mjSRshnLy8sD4LPPPmPp0qXO6fHx8fFs2LCBMWPGsHPnTjw9PamtraW4uJioqCg8PT3JzMxk27Zt5Ofn4+bmxujRo0lPT2fq1Kk35VW5vqxWK/7+/hQXF1NSUmI0Rf+SjIwMBg8e7PI1KZbbUEJCArm5uYSGhhIREUH79u3ZuHEjBQUFJCYmApCbm8u4ceOcT76JEyeyaNEipk6desN9N/Up+qmpqezfv58PPvjA5WvRadhtKCkpiby8PHJzc0lISCAxMfGKy/D3E/j/biJ/c5KWlkZ2djZr1qzBy8vL5fvXO8ttwMfHhxMnTjgvd+rUCR8fHxYvXkx2djZt27ZlxowZnDx5EpvNBkBiYiLLli1j5MiRtGjRgiVLljjfdW6kqU7Rnz9/Pl988QVZWVm0adPmpqxJsdwGJk+ezLPPPouXlxfp6enYbDYSExPJycmha9euAHTo0IGoqCjnu8ekSZM4cOAA/fr1A6Bv375Mnjy50e7D1eozRf/QoUPMnDmToKAghg4dCvz1GwY2bNjg0jVpin4j0xT9xqcp+iIuplhEDCkWEUOKRcSQYhExpFhEDCkWEUOKRcSQYhExpFhEDCkWEUP62TARQ3pnETGkWEQMKRYRQ4pFxJBiETGkWEQMKRYRQ4pFxJBiETGkWEQMKRYRQ4pFxJBiETGkWEQMKRYRQ4pFxJBiETGkWEQMKRYRQ/8DvQqBOghZLnkAAAAASUVORK5CYII=",
      "text/plain": [
       "<Figure size 183x124 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "from diagram import diagram, adjust, Bbox\n",
    "\n",
    "width, height, x, y = [1.83, 1.24, 0.49, 0.85]\n",
    "ax = diagram(width, height)\n",
    "bbox = binding1.draw(ax, x, y)\n",
    "# adjust(x, y, bbox)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b092aa61",
   "metadata": {},
   "source": [
    "字典用盒子表示，上方用“dict”标识，内部是它包含的项。每个项用键和箭头指向的值表示。引号表示键是字符串，而不是变量的名字。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2a0a128a",
   "metadata": {},
   "source": [
    "## 创建字典\n",
    "\n",
    "我们之前创建了空的字典，使用方括号运算符每次添加一个项。然而，我们可以像这样一次性创建字典："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "19dfeecb",
   "metadata": {},
   "outputs": [],
   "source": [
    "numbers = {'zero': 0, 'one': 1, 'two': 2}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "31ded5b2",
   "metadata": {},
   "source": [
    "每个项由冒号分隔的键和值组成。这些项之间用逗号分隔，整体用花括号包围。\n",
    "\n",
    "使用`dict`函数是创建字典的另一种方法。我们可以像这样创建空字典："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "39b81034",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{}"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "empty = dict()\n",
    "empty"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bfb215c9",
   "metadata": {},
   "source": [
    "我们也可以像这样创建字典的副本："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "88fa12c5",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'zero': 0, 'one': 1, 'two': 2}"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "numbers_copy = dict(numbers)\n",
    "numbers_copy"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "966c5539",
   "metadata": {},
   "source": [
    "在修改字典之前创建副本通常是很有用的。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2a948f62",
   "metadata": {
    "tags": []
   },
   "source": [
    "## in运算符\n",
    "\n",
    "`in`运算符也对字典有效。它告诉你一个对象是否在字典的*键*中。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "025cad92",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'one' in numbers"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "80f6b264",
   "metadata": {},
   "source": [
    "`in`运算符*不*检查一个对象是否在字典的值中。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "65de12ab",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "1 in numbers"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "84856c8b",
   "metadata": {},
   "source": [
    "要检查一个对象是否在字典的值中，你可以使用字典的方法`values`，返回一组值，然后使用`in`运算符。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "87ddc1b2",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "1 in numbers.values()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "45dc3d16",
   "metadata": {},
   "source": [
    "Python字典中的项存储在**哈希表hash table**中，哈希表是一种组织数据的方式，特点在于：无论有多少项，`in`运算符花费的时间基本相等。这让编写十分高效的算法成为可能。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "4849b563",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "download('https://gitee.com/regentsai/Think_Python_3e_CN/blob/master/words.txt');"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bba0522c",
   "metadata": {},
   "source": [
    "为了演示这一点，我们将比较两种算法，分别寻找所有翻转的单词对，比如`stressed`和`desserts`。我们首先读取单词列表。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "830b1208",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "113783"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "word_list = open('words.txt').read().split()\n",
    "len(word_list)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ab29fb8a",
   "metadata": {},
   "source": [
    "以下是之前章节使用的`reverse_word`翻转单词函数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "49231201",
   "metadata": {},
   "outputs": [],
   "source": [
    "def reverse_word(word):\n",
    "    return ''.join(reversed(word))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "93f7ac1b",
   "metadata": {},
   "source": [
    "以下函数遍历列表中的单词，对于每个单词，翻转单词，然后检查翻转的单词是否在单词列表中。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "a41759fb",
   "metadata": {},
   "outputs": [],
   "source": [
    "def too_slow():\n",
    "    count = 0\n",
    "    for word in word_list:\n",
    "        if reverse_word(word) in word_list:\n",
    "            count += 1\n",
    "    return count"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d4ebb84d",
   "metadata": {},
   "source": [
    "这个函数需要运行超过1分钟。问题在于`in`运算符从头开始，一次检查一个列表中的单词。如果它没有找到需要的值（这是多数时候的情况），它必须一直搜索到结尾。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "33bcddf8",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# %time too_slow()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2acb6c50",
   "metadata": {},
   "source": [
    "`in`运算符在循环中，所以它需要对每个单词执行一次检查。由于列表中有超过10万个单词，每个单词要比较超过10万个单词，比较的总次数是单词数的平方，大约1.3千万次。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "f2869dd0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12946571089"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(word_list)**2"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5dbf01b7",
   "metadata": {},
   "source": [
    "用列表会快得多。接下来的循环创建一个字典，将所有单词作为键。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "300416d9",
   "metadata": {},
   "outputs": [],
   "source": [
    "word_dict = {}\n",
    "for word in word_list:\n",
    "    word_dict[word] = 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b7f6a1b7",
   "metadata": {},
   "source": [
    "`word_dict`的所有值都是`1`，但它们可以是任何东西，因为我们永远不会查找它们，我们只会用字典检查键是否存在。\n",
    "\n",
    "现在我们将`word_list`替换为`word_dict`，新版本的函数如下："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "9d3dfd8d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def much_faster():\n",
    "    count = 0\n",
    "    for word in word_dict:\n",
    "        if reverse_word(word) in word_dict:\n",
    "            count += 1\n",
    "    return count"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5f41e54c",
   "metadata": {},
   "source": [
    "这个函数花费时间少于1秒，远比之前的版本快。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "82b36568",
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 41.2 ms, sys: 73 μs, total: 41.2 ms\n",
      "Wall time: 41.1 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "885"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time much_faster()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4cd91c99",
   "metadata": {},
   "source": [
    "大致上，在列表中寻找一个元素的时间与列表的长度成比例。而在字典中寻找一个键的时间几乎是固定的，不管有多少项。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b3bfa8a5",
   "metadata": {},
   "source": [
    "## 计数器的集合\n",
    "\n",
    "假设你有一个字符串，你想要计算每个字母出现的次数，字典是执行这个工作的好工具。我从一个空的字典开始。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "7c21ff00",
   "metadata": {},
   "outputs": [],
   "source": [
    "counter = {}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "34a9498a",
   "metadata": {},
   "source": [
    "我们遍历字符串中的字母，假设我们第一个看到的是`'a'`。我们可以像这样将其添加到字典中："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "7d0afb00",
   "metadata": {},
   "outputs": [],
   "source": [
    "counter['a'] = 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bca9fa11",
   "metadata": {},
   "source": [
    "`1`这个值表示我们已经见过1次字母了。稍后，如果我们再次见到相同的字母，我们可以像这样增加："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "ba97b5ea",
   "metadata": {},
   "outputs": [],
   "source": [
    "counter['a'] += 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "274ea014",
   "metadata": {},
   "source": [
    "现在与`'a'`联系的值为`2`，因为我们已经见过2次这个字母了。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "30ffe9b4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'a': 2}"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "counter"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2ca8f99d",
   "metadata": {},
   "source": [
    "下面的函数使用这些功能，计算字符串中每个字母出现过的次数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "36f95332",
   "metadata": {},
   "outputs": [],
   "source": [
    "def value_counts(string):\n",
    "    counter = {}\n",
    "    for letter in string:\n",
    "        if letter not in counter:\n",
    "            counter[letter] = 1\n",
    "        else:\n",
    "            counter[letter] += 1\n",
    "    return counter"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "735c758b",
   "metadata": {},
   "source": [
    "循环中的每个轮次，如果`letter`不在字典中，我们创建新的项，键为对应的`letter`，值为`1`。如果`letter`已经在字典中，我们增加与`letter`联系的值。\n",
    "以下是一个例子："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "d6f1048e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'b': 1, 'r': 2, 'o': 2, 'n': 1, 't': 1, 's': 2, 'a': 1, 'u': 2}"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "counter = value_counts('brontosaurus')\n",
    "counter"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8ac1fea4",
   "metadata": {},
   "source": [
    "`counter`中的项表明字典`'b'`出现了1次，`'r'`出现了2次，以此类推。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "912bdf5d",
   "metadata": {},
   "source": [
    "## 循环和字典\n",
    "\n",
    "如果你在`for`语句中使用字典，它将遍历字典的所有键。例如，让我们创建一个计算`banana`字母数量的字典："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "310e1489",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'b': 1, 'a': 3, 'n': 2}"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "counter = value_counts('banana')\n",
    "counter"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fe263f3d",
   "metadata": {},
   "source": [
    "以下循环将打印字典的键，在这个例子里是组成单词的字母："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "da4ec7fd",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "b\n",
      "a\n",
      "n\n"
     ]
    }
   ],
   "source": [
    "for key in counter:\n",
    "    print(key)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bf1b7824",
   "metadata": {},
   "source": [
    "要打印值，我们可以使用`values`方法。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "859fe1ad",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "3\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "for value in counter.values():\n",
    "    print(value)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "721135be",
   "metadata": {},
   "source": [
    "要同时打印键和值，我们可以遍历键，同时查找对应的值。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "7242ab5b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "b 1\n",
      "a 3\n",
      "n 2\n"
     ]
    }
   ],
   "source": [
    "for key in counter:\n",
    "    value = counter[key]\n",
    "    print(key, value)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "efa1bce5",
   "metadata": {},
   "source": [
    "在下一章，我们将看到解决这个需求的更简洁的方法。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a160c0ef",
   "metadata": {},
   "source": [
    "## 列表和字典\n",
    "\n",
    "你可以将列表作为字典的值。例如，以下是一个字典，将数字`4`映射到一个4个字母的列表。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "29cd8207",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{4: ['r', 'o', 'u', 's']}"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d = {4: ['r', 'o', 'u', 's']}\n",
    "d"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "815a829f",
   "metadata": {},
   "source": [
    "但你不能将列表作为字典的键。以下是这样做的结果："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "ca9ff511",
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "unhashable type: 'list'",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31mTypeError\u001b[0m\u001b[0;31m:\u001b[0m unhashable type: 'list'\n"
     ]
    }
   ],
   "source": [
    "%%expect TypeError\n",
    "letters = list('abcd')\n",
    "d[letters] = 4"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2469b08a",
   "metadata": {},
   "source": [
    "我之前提到字典使用哈希表，这意味着键必须是**可哈希的 hashable**。**哈希hash**是一个函数，接受一个值，返回一个整数。字典使用这些整数（称为哈希值）执行键的存储和查找。\n",
    "\n",
    "这种系统只有在键是不可变的时候才有效，以确保一个键的哈希值总是相同的。如果键是可变的，它的哈希值也可能改变，导致字典失效。因此键必须是可哈希的，可变类型（如列表）不能是键。\n",
    "\n",
    "由于字典是可变的，它们也不能是键。但它们*可以*作为值。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "acfd2720",
   "metadata": {
    "tags": []
   },
   "source": [
    "## 累集列表\n",
    "\n",
    "对于许多编程任务，遍历一个列表或字典的同时创建另一个是很有用的。比如，我们将遍历`word_dict`中的单词，创建一个回文词列表。回文词是正反拼写顺序相同的单词，如noon和rotator。\n",
    "\n",
    "在上一章，有一个练习要求你编写函数，检查单词是否为回文词。以下是使用`reverse_word`的一种方案："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "0647278e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_palindrome(word):\n",
    "    \"\"\"检查单词是否是回文词。\"\"\"\n",
    "    return reverse_word(word) == word"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "af545fcd",
   "metadata": {},
   "source": [
    "如果我们遍历`word_dict`中的单词，我们可以计算回文词的数量："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "id": "9eff9f2c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "91"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "count = 0\n",
    "\n",
    "for word in word_dict:\n",
    "    if is_palindrome(word):\n",
    "        count +=1\n",
    "        \n",
    "count"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "73c1ce1e",
   "metadata": {},
   "source": [
    "目前为止，这个模式令人熟悉：\n",
    "\n",
    "- 循环之前`count`初始化为`0`；\n",
    "- 循环内部，如果`word`是回文词，增加`count`的值；\n",
    "- 循环结束时，`count`包含回文词的总数。\n",
    "\n",
    "我们可以用相似的模式创建一个回文词的列表。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "609bdd9a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['aa', 'aba', 'aga', 'aha', 'ala', 'alula', 'ama', 'ana', 'anna', 'ava']"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "palindromes = []\n",
    "\n",
    "for word in word_dict:\n",
    "    if is_palindrome(word):\n",
    "        palindromes.append(word)\n",
    "\n",
    "palindromes[:10]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "be909f3b",
   "metadata": {},
   "source": [
    "- 循环之前`palindromes`初始化为空列表；\n",
    "- 循环内部，如果`word`是回文词，将其追加到`palindromes`末尾；\n",
    "- 循环结束时，`palindromes`是包含所有回文词的列表。\n",
    "\n",
    "在这个循环中，`palindromes`用作**累集器accumulator**，它是一个变量，在计算过程中收集或者累集数据。\n",
    "\n",
    "现在假设我们只想要选中长度>=7的回文词。我们可以遍历`palindromes`，创建新的列表，只包含长的回文词。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "c2db1187",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['deified', 'halalah', 'reifier', 'repaper', 'reviver', 'rotator', 'sememes']"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "long_palindromes = []\n",
    "\n",
    "for word in palindromes:\n",
    "    if len(word) >= 7:\n",
    "        long_palindromes.append(word)\n",
    "        \n",
    "long_palindromes"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fa8ed275",
   "metadata": {},
   "source": [
    "像这样遍历列表，选择某些元素，忽略其他元素的过程称为**过滤filtering**。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8ed50837",
   "metadata": {
    "tags": []
   },
   "source": [
    "## 备忘录\n",
    "\n",
    "如果你运行[第6章](chap06.ipynb)中的`fibonacci`函数，你可能注意到提供的参数越大，函数执行的时间更长。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "13a7ed35",
   "metadata": {},
   "outputs": [],
   "source": [
    "def fibonacci(n):\n",
    "    if n == 0:\n",
    "        return 0\n",
    "    \n",
    "    if n == 1:\n",
    "        return 1\n",
    "\n",
    "    return fibonacci(n-1) + fibonacci(n-2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1b5203c2",
   "metadata": {},
   "source": [
    "而且，运行的时间增长的速度很快。要理解为什么，考虑以下图像，展示参数`n=4`的`fibonacci`的**调用图 call graph**："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "id": "7ed6137a",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "from diagram import make_binding, Frame, Arrow\n",
    "\n",
    "bindings = [make_binding('n', i) for i in range(5)]\n",
    "frames = [Frame([binding]) for binding in bindings]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "a9374c39",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "arrowprops = dict(arrowstyle=\"-\", color='gray', alpha=0.5, ls='-', lw=0.5)\n",
    "\n",
    "def left_arrow(ax, bbox1, bbox2):\n",
    "    x = bbox1.xmin + 0.1\n",
    "    y = bbox1.ymin\n",
    "    dx = bbox2.xmax - x - 0.1\n",
    "    dy = bbox2.ymax - y\n",
    "    arrow = Arrow(dx=dx, dy=dy, arrowprops=arrowprops)\n",
    "    return arrow.draw(ax, x, y)\n",
    "\n",
    "def right_arrow(ax, bbox1, bbox2):\n",
    "    x = bbox1.xmax - 0.1\n",
    "    y = bbox1.ymin\n",
    "    dx = bbox2.xmin - x + 0.1\n",
    "    dy = bbox2.ymax - y\n",
    "    arrow = Arrow(dx=dx, dy=dy, arrowprops=arrowprops)\n",
    "    return arrow.draw(ax, x, y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "id": "12098be7",
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAgIAAADsCAYAAAAGlM4XAAAAOnRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjEwLjAsIGh0dHBzOi8vbWF0cGxvdGxpYi5vcmcvlHJYcgAAAAlwSFlzAAAPYQAAD2EBqD+naQAAFExJREFUeJzt3U9om+cBx/GfZNmSZUuNbMt+hV0nt4QRB3JoegiEGsrqQmnaQ8hGdlguo1AYoaM59NZDGWNhaUsP2TGQBVqcgsnI3IVgSimjGbTLxWSjWx3wP0l27FiyLNuS3h2GTbr4j2xLeqT3+X5ODsi8P/L4kX563vd5X5/ruq4AAICV/KYDAAAAcygCAABYjCIAAIDFKAIAAFiMIgAAgMUoAgAAWIwiAACAxSgCAABYjCIAAIDFKAIAAFiMIgAAgMUoAgAAWIwiAACAxSgCAABYjCIAAIDFKAIAAFiMIgAAgMUoAgAAWIwiAACAxQKmAwCovkwmYzpCQ4hEIqYjADXHigAAABajCAAAYDGKAAAAFqMIAABgMYoAAAAWowgAAGAxigAAABajCAAAYDGKAAAAFqMIAPCk3/72t4pGoxofHzcdBahrFAEAnvOPf/xDf//73/X888+bjgLUPYoAgB+JRqO6evWqBgcHNTAwoBs3bhjNMzExoZs3b2p8fFylUmnX16+uruo3v/mN/vCHP8jn89UgIdDYKAIAnhEMBjU2Nqbh4WFdvnxZhULBWJZ4PK62tjaNjo7q+vXruxaCDz74QOfPn9eRI0dqFxJoYDx9EMAzzp8/L0k6evSoAoGAksmkent7f/Sa+/fva3p6umaZent7tbCwoNHRUd27d0/nzp2T4zg/es0333yjb7/9Vu+//37NcgGNjhUBAM8IBoObP/v9fqMrAnvx9ddf61//+pcGBgZ0/PhxTU1N6c0339Rf//pX09GAuuVzXdc1HQJAdWUymbJfG41GNT09rfb2dknSkSNH9OWXX+rw4cPVirej5eVl3b17V//5z38Ui8X04osv6tixY/L7d/8ec/z4cX322Wf6yU9+UtaxIpHIQeMCDYdTAwDqWjqdVi6X09DQUNkFAED5WBEALLCXFQGbsSIAG1GtAQCwGEUAAACLUQQAALAYRQAAAItRBAAAsBhFAAAAi1EEAACwGEUAAACLUQQAALAYRQAAAItRBAAAsBjPGgCglZUVFYvFzScOel0ul1Nzc7Oam5tNRwGM4+mDgKUKhYLS6bTm5ubU0tKi3t5e05FqplAo6IcffpDP55PjOIrFYvL5fKZjAUawIgBYxHVdPX78WKlUSsViUfF4XF1dXWpqajIdzYjV1VXNzs5qYWFBsVhMjuMoGAyajgXUFEUAsEA2m1UymVQ2m1UsFlNPTw8feE9xXVeLi4uamZmR67rq6elRZ2cnqwSwAkUA8Ki1tTWlUinNz88rHA7LcRy1t7fz4baL9fV1zc7O6vHjx4pEIkokEmptbTUdC6gaigDgIaVSSXNzc0qn0/L5fOru7lZHR4f8fjYI7ZXrulpaWtLMzIzW19fV09Ojrq4u/i/hORQBoMFtfGAlk0nl83l1dnaqu7ubK+IrqFAoKJVKKZ1Oq62tTYlEQm1tbaZjARVBEQAaVD6fVzKZ1OLioiKRiBzHUTgcNh3L8zKZjGZnZ7WysqJ4PK7u7m5rL7aEN1AEgAby9Ja/5uZm9fT06NChQ5z3N6BYLCqdTiudTqulpUWJREKRSISxQMOhCAB1znVdLSwsKJlMqlAoKB6PKx6P8y20juRyOc3MzCibzaqrq4tTM2goFAGgTi0vLyuZTCqTyejQoUPq6elRKBQyHQs7KJVKmp+fVzKZVFNTkxKJhJ577jlWCVDXKAJAHdnY8vf48WO1traqp6eH5eYGlc/nNTs7qydPnmzerKilpcV0LOAZFAHAsI1vkalUSpLU3d2tzs5Otql5xMbdHJPJpFzXleM46ujooNyhblAEAANc1928+pwtf/ZYW1vbvKXxc889J8dxON0D4ygCQA39/5a/np4e9qNbyHVdPXnyRDMzMyoWi5u3NGYVCCZQBIAqe3qbWSAQkOM4bPnDpvX1daVSKc3Nzam9vV2JRIL7QaCmKAJAFWw8xCaZTGp9fX3zKX+BAE/+xtY2ThfNzMxobW2NbaKoGYoAUEG5XE6zs7Ns+cOBFIvFzVsat7a2KpFIqL293XQseBRFADigjaXd+fl5hUIhOY7Dlj9UzPLysmZmZpTL5TZvVsTKEiqJIgDsQ6lU0uPHj5VKpeS6Llv+UHUbT5ZMJpNqbm5WIpFQNBqlcOLAKAJAmVzXVTab3XzgTEdHh7q7u7lJDGpuZWVFMzMzymQy6ujokOM4bD3FvlEEgF2srq4qmUxqYWFB7e3tchyHLX+oC67rbt7S2OfzKZFIsCMFe0YRALZQLBY1NzendDqtpqYm9fT0KBaL8QaLurW6uqrZ2VktLi7q0KFDchxHwWDQdCw0AIoA8JRsNqvJyUmtr6+rq6tL8XicC7PQUDa2rs7MzMh1XT3//POKRqOmY6GOUQSAp2SzWTU1Nam1tdV0FODA1tfXtb6+zg2KsCOKACRJmUzGdISGEIlETEcAnsH8LQ/zd2vsdQIAwGIUAQAALEYRAADAYhQBAAAsRhEAAMBiFAEAACxGEQAAwGIUAQAALEYRAADAYtxEHdY5e/asUqmU/H6/2tvb9fvf/14nTpwwHQvALvL5vC5evKiHDx8qHA6ru7tbH374oQ4fPmw6WkPjFsOQZNctSjeeziZJf/7zn/W73/1OX331VVm/yy1KUY9smb/5fF5ffvmlfvrTn8rn8+mPf/yj7ty5o5GRkbJ+n/m7NU4NYM+i0aiuXr2qwcFBDQwM6MaNG0bzTExM6ObNmxofH1epVNr19RslQJKePHkiv59pAHs08vwNhUJ65ZVXNh8H/sILL2hiYqIGKb2NUwPYl2AwqLGxMf3zn//U4OCgfvaznxl7XG88HldbW5tGR0f1zTff6MUXX9SxY8d2/ID/1a9+tbkK8Pnnn9cqKlAXGn3+brh27ZpeffXVGqT0Nk4NQNLelhaj0ah++OEHdXZ2SpL6+/v1t7/9Tb29vT963f379zU9PV3RnDtZXV3VwsKCcrmcmpubde7cOTmOs+Pv/OlPf9Lnn3+uW7dulXUMlhZRj2ycv1euXNFf/vIX3b59u+zHLDN/t8aaKPYlGAxu/uz3+1UoFAym2b8LFy7oq6++0vz8vOkoQM00+vz9+OOPdfv2bd26davsEoDtcWoAVXPq1KmaHGd5eVl3797V1NSUYrGYzpw5s+3S4tLSkpaXl5VIJCRJt2/fVkdHhzo6OmqSFWgU9Th/JemTTz7R8PCwRkZGfnS9D/aPIoCGl06nlcvlNDQ0tOu5xaWlJf3iF79QPp+X3+9XV1eXPvvss82LjwDU1l7m79TUlN577z0dOXJEr732miSppaVFY2NjtYrrSVwjAEn2bD86KM4xoh4xf8vD/N0a1wgAAGAxigAAABajCAAAYDGKAAAAFqMIAABgMYoAAAAWowgAAGAxigAAABajCAAAYDGKAAAAFqMIAABgMZ41AACAxVgRAADAYhQB7Ekmk9HS0pLpGFWTSqVMRwCqhvmLrVAEsCezs7MKBAKmY1RNKpVSqVQyHQOoCuYvtkIRQNlc11Uul1M4HDYdpWpCoZDy+bzpGEDFMX+xHYoAypbNZhWJREzHqKpwOKyVlRXTMYCKY/5iOxQBlG1ubk6dnZ2mY1RVa2urcrmc6RhAxTF/sR2KAMqWyWQUjUZNx6iqcDjMGwk8ifmL7VAEUJaVlRUFg0H5fD7TUaqqpaVFa2trpmMAFcX8xU4oAijL/Py8urq6TMeoOq+/UcJOzF/shCKAsiwsLCgWi5mOURNNTU0qFAqmYwAVw/zFTigC2NX6+rqamprk99vx59La2sqVx/AM5i92Y8dfBg5kfn5eHR0dpmPUDBccwUuYv9gNRQC7mp+f9/y2o6exFxlewvzFbigC2FGxWFSpVFJzc7PpKDXDXmR4BfMX5aAIYEeLi4vWXGS0IRAIqFgsmo4BHBjzF+WgCGBHc3NzVmw72orruqYjAAfC/EU5KALYluu6yufzCoVCpqPUHDcmQaNj/jJ/y0URwLaWlpY8f0vS7XDBERod85f5Wy6KALZl87IiFxyh0TF/mb/loghgW9lsVu3t7aZjGME3CjQ65i/zt1wUAWwpl8spHA5be+/uUCjEGwkaFvOX+bsXFAFsqVAoyHEc0zGM8fv96u7uNh0D2BfmL/N3L3wueywAALAWKwIAAFgsYDpAvcpkMqYjNIRIJGI6wr4wvuVhfL2N8fW2cseXFQEAACxGEQAAwGIUAQAALEYRAADAYhQBAAAsRhEAAMBiFAEAACxGEQAAwGIUAQAALEYRsFw+n9fPf/5znTx5UqdPn9abb76pR48emY6FCnn33Xd1/PhxRaNRjY+Pm46DCmN8ve/777/Xyy+/rJMnT+qll17Sw4cPK34MigD0y1/+Ut9++62+/vprDQ0N6de//rXpSKiQN954Q1988YX6+/tNR0EVML7ed+nSJV28eFHfffedLl26pLfffrvix6AIVEA0GtXVq1c1ODiogYEB3bhxw2ieiYkJ3bx5U+Pj4yqVSju+NhQK6ZVXXtl8bvkLL7ygiYmJGqRsHI08vqdPn1Zvb2+NkjUmxtfbGnl80+m0Hjx4oPPnz0uSzp49q0ePHlV81ZYiUCHBYFBjY2MaHh7W5cuXVSgUjGWJx+Nqa2vT6Oiorl+/XtYf3IZr167p1VdfrXLCxuOV8cXWGF9va9TxnZyclOM4CgT+93xAn8+nvr4+TU5OVjQTTx+skI3GdvToUQUCASWTyWea+v379zU9PV2zTL29vVpYWNDo6Kju3bunc+fOyXGcbV9/5coV/fvf/9aHH35Ys4yNwgvji+0xvt7WyOO7sVq7wXXdimdhRaBCgsHg5s9+v99o49yPjz/+WLdv39atW7cUDodNx6k7jT6+2Bnj622NOr59fX2anp7ezOu6rqamptTX11fR47AiUEOnTp2qyXGWl5d19+5dTU1NKRaL6cyZMzp27Jj8/q173yeffKLh4WGNjIzo0KFDNcnoRfU6vqgMxtfb6nF84/G4Tpw4oU8//VQXLlzQyMiI+vv7dfjw4Ypmogh4UDqdVi6X09DQ0K5vIFNTU3rvvfd05MgRvfbaa5KklpYWjY2N1Sou9mgv4/vOO+/ozp07SiaTev3119XW1qYHDx7UMC32ivH1tr2MryR99NFHeuutt3TlyhVFo1Fdu3at4pl8bjVOOHhAJpMxHaEhRCIR0xH2hfEtD+PrbYyvt5U7vqw1AQBgMYoAAAAWowgAAGAxigAAABajCAAAYDGKAAAAFqMIAABgMYoAAAAWowgAAGAxigAAABajCAAAYDGeNQAAgMVYEQAAwGIUgQPKZDJaWloyHaNqUqmU6QgAgCqiCBzQ7OysAoGA6RhVk0qlVCqVTMcAAFQJReAAXNdVLpdTOBw2HaVqQqGQ8vm86RgAgCqhCBxANptVJBIxHaOqwuGwVlZWTMcAAFQJReAA5ubm1NnZaTpGVbW2tiqXy5mOAQCoEorAAWQyGUWjUdMxqiocDlMEAMDDKAL7tLKyomAwKJ/PZzpKVbW0tGhtbc10DABAlVAE9ml+fl5dXV2mY1Sd14sOANiOIrBPCwsLisVipmPURFNTkwqFgukYAIAqoAjsw/r6uvx+v/x+O/77Wltb2TkAAB5lxydZhc3Pz3t+t8DTuGAQALyLIrAPNhYBVgQAwJsoAntULBZVKpXU3NxsOkrNcC8BAPAuisAeLS4uWnOR4IZAIKBisWg6BgCgCigCezQ3N2fFtsGtuK5rOgIAoMIoAnvguq7y+bxCoZDpKDXHjYUAwJsoAnuwtLTk+VsKb4cLBgHAmygCe2DzaQEuGAQAb6II7EE2m1V7e7vpGEawIgAA3kQRKFMul1M4HLb23vuhUIgiAAAeRBEoU6FQkOM4pmMY4/f71d3dbToGAKDCfC57wgAAsBYrAgAAWCxQ7gszmUw1c3hGJBIxHWFfGN/yNOr4AsB2WBEAAMBiFAEAACxGEQAAwGIUAQAALEYRAADAYhQBAAAsRhEAAMBiFAEAACxGEQAAwGIUgf/z7rvv6vjx44pGoxofHzcdB1Xw/fff6+WXX9bJkyf10ksv6eHDh6YjAYAxFIH/88Ybb+iLL75Qf3+/6SiokkuXLunixYv67rvvdOnSJb399tumIwGAMVUpAtFoVFevXtXg4KAGBgZ048aNahymbBMTE7p586bGx8dVKpV2fO3p06fV29tbo2SNqZHHN51O68GDBzp//rwk6ezZs3r06JEePXpUi6gAUHeqtiIQDAY1Njam4eFhXb58WYVCoVqH2lU8HldbW5tGR0d1/fr1sj4wsLNGHd/JyUk5jqNA4H/P2/L5fOrr69Pk5GQtIwNA3Sj76YN7tfGN6+jRowoEAkomk898075//76mp6erFeEZvb29WlhY0OjoqO7du6dz587JcZyaHd9LGnl8fT7fj/7tum6tIgJA3anqisDmQfx+o98YUXmNOr59fX2anp7ezOu6rqamptTX12c4GQCYUbUVgXKcOnWqJsdZXl7W3bt3NTU1pVgspjNnzujYsWPy+7lWsprqcXzj8bhOnDihTz/9VBcuXNDIyIj6+/t1+PDhmmQFgHpjtAjUSjqdVi6X09DQ0K4F4J133tGdO3eUTCb1+uuvq62tTQ8ePKhhWuzVXsZXkj766CO99dZbunLliqLRqK5du1ajpABQf3xumSdIM5lMtbN4QiQSMR1hXxjf8jTq+ALAdlgbBwDAYhQBAAAsRhEAAMBiFAEAACxGEQAAwGIUAQAALEYRAADAYhQBAAAsRhEAAMBiFAEAACxGEQAAwGJlP2sAAAB4DysCAABYjCIAAIDFKAIAAFiMIgAAgMUoAgAAWIwiAACAxSgCAABYjCIAAIDFKAIAAFiMIgAAgMUoAgAAWIwiAACAxSgCAABYjCIAAIDFKAIAAFiMIgAAgMUoAgAAWIwiAACAxSgCAABYjCIAAIDF/gtYN0GRS14D0gAAAABJRU5ErkJggg==",
      "text/plain": [
       "<Figure size 494x216 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "from diagram import diagram, adjust, Bbox\n",
    "\n",
    "width, height, x, y = [4.94, 2.16, -1.03, 1.91]\n",
    "ax = diagram(width, height)\n",
    "\n",
    "dx = 0.6\n",
    "dy = 0.55\n",
    "\n",
    "bboxes = []\n",
    "bboxes.append(frames[4].draw(ax, x+6*dx, y))\n",
    "\n",
    "bboxes.append(frames[3].draw(ax, x+4*dx, y-dy))\n",
    "bboxes.append(frames[2].draw(ax, x+8*dx, y-dy))\n",
    "\n",
    "bboxes.append(frames[2].draw(ax, x+3*dx, y-2*dy))\n",
    "bboxes.append(frames[1].draw(ax, x+5*dx, y-2*dy))\n",
    "bboxes.append(frames[1].draw(ax, x+7*dx, y-2*dy))\n",
    "bboxes.append(frames[0].draw(ax, x+9*dx, y-2*dy))\n",
    "\n",
    "bboxes.append(frames[1].draw(ax, x+2*dx, y-3*dy))\n",
    "bboxes.append(frames[0].draw(ax, x+4*dx, y-3*dy))\n",
    "\n",
    "left_arrow(ax, bboxes[0], bboxes[1])\n",
    "left_arrow(ax, bboxes[1], bboxes[3])\n",
    "left_arrow(ax, bboxes[3], bboxes[7])\n",
    "left_arrow(ax, bboxes[2], bboxes[5])\n",
    "\n",
    "right_arrow(ax, bboxes[0], bboxes[2])\n",
    "right_arrow(ax, bboxes[1], bboxes[4])\n",
    "right_arrow(ax, bboxes[2], bboxes[6])\n",
    "right_arrow(ax, bboxes[3], bboxes[8])\n",
    "\n",
    "bbox = Bbox.union(bboxes)\n",
    "# adjust(x, y, bbox)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4ee2a87c",
   "metadata": {},
   "source": [
    "调用图显示一组函数帧，将函数和它调用的函数用直线相连。在调用图的顶端，`n=4`的`fibonacci`调用`n=3`以及`n=2`的函数；然后，`n=3`的`fibonacci`调用`n=2`以及`n=1`的函数，以此类推。\n",
    "\n",
    "你可以数一数`fibonacci(0)`和`fibonacci(1)`调用了多少次。这是一种不高效的解法，当参数更大时会变得更糟。\n",
    "\n",
    "一种解决方法是记录已经计算过的函数值，存储在字典中。将之前计算的结果保存，以便后续使用的值称为**备忘录memo**。以下是有备忘功能的`fibonacci`版本："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "id": "28e443f5",
   "metadata": {},
   "outputs": [],
   "source": [
    "known = {0:0, 1:1}\n",
    "\n",
    "def fibonacci_memo(n):\n",
    "    if n in known:\n",
    "        return known[n]\n",
    "\n",
    "    res = fibonacci_memo(n-1) + fibonacci_memo(n-2)\n",
    "    known[n] = res\n",
    "    return res"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d2ac4dd7",
   "metadata": {},
   "source": [
    "`known`是保存已知的Fibonacci数字典。它最开始包含两项：`0`映射到`0`，`1`映射到`1`。\n",
    "\n",
    "当调用`fibonacci_memo`时，它会检查`known`。如果结果已经在`known`中，它可以立即返回结果。否则它会计算新值，添加进字典，然后返回结果。\n",
    "\n",
    "比较两个函数，`fibonacci(40)`花费约30秒，而`fibonacci_memo(40)`花费约30微秒，所以大约快一百万倍。在本章的笔记中你将看到这些时间的出处。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c6f39f84",
   "metadata": {
    "tags": []
   },
   "source": [
    "要计算函数花费多久，我们可以使用`%time`，它是Jupyter的内建“魔术命令”。这些命令不是Python语言的一部分，对其他开发环境可能无效。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "id": "af818c11",
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 10.9 s, sys: 4.51 ms, total: 10.9 s\n",
      "Wall time: 10.9 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "102334155"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time fibonacci(40)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "id": "7316d721",
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 10 μs, sys: 0 ns, total: 10 μs\n",
      "Wall time: 13.4 μs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "102334155"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time fibonacci_memo(40)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ec969e51",
   "metadata": {},
   "source": [
    "## 调试\n",
    "\n",
    "当你处理更大的数据集时，使用打印语句并亲自检查输出可能是不明智的。以下是调试大数据集的一些建议：\n",
    "\n",
    "1. 缩小输入数量：如果可能的话，减少数据集的大小。例如，如果程序读取文本文件，从读取前10行开始；或者使用尽可能小的样本。你可以修改文件，或者修改程序（更好），只读取前`n`行。如果出现错误，你可以减少`n`，直到错误发生的最小值。当你发现并改正了错误，你可以慢慢增加`n`。\n",
    "2. 检查汇总信息和类型：考虑打印数据的汇总信息而不是打印和检查整个数据集，比如字典中的项数或者数字列表的总和。运行时错误中值的类型错误是常见的错误，打印值的类型通常够用。\n",
    "3. 编写自动检查：你可以编写代码自动检查错误。例如，如果你在计算数字列表的平均值，你可以将结果与最大值或最小值比较。这叫作“合理性检查sanity check”，因为它检测“疯狂insane”的结果;另一种检查比较两次不同的计算结果是否一致，叫作“一致性检查”。\n",
    "4. 格式化输出：带有格式的调试输出让我们更容易发现错误。在[第6章](chap06.ipynb)中有一个例子。另一个可能有用的工具为`pprint`模块,提供`pprint`函数，以可读性更高的格式显示内建的类型对象（`pprint`表示漂亮的打印\"pretty print\"）。再次提醒，花时间搭建脚手架可以节省调试时间。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9820175f",
   "metadata": {},
   "source": [
    "## 术语表\n",
    "\n",
    "- **字典dictionary**：包含键-值对的对象，键-值对也叫作项；\n",
    "- **项item**：字典中键-值对的别称；\n",
    "- **键key**：在字典中出现的对象，作为键-值对的第1部分；\n",
    "- **值value**：在字典中出现的对象，作为键-值对的第2部分。这个叫法比我们之前使用的\"值value\"更具体；\n",
    "- **映射mapping**：一个集合的元素与另一个集合的元素的关系；\n",
    "- **哈希表hash table**：键-值对的合集，当我们查找键时，能够高效地找到值；\n",
    "- **可哈希的hashable**：不可变的类型是可哈希的，例如整数，符点数，字典；可变类型不是可哈希的，如列表或字典；\n",
    "- **哈希函数hash function**：接受一个对象，计算一个整数的函数，用于定位哈希表中的键；\n",
    "- **累集器accumulator**：在循环中使用的变量，将结果进行求和或者收集；\n",
    "- **过滤filtering**：遍历一个序列，选择或者忽略部分元素；\n",
    "- **调用图call graph**：显示程序执行期间创建的所有帧的图，箭头从调用函数指向被调用函数；\n",
    "- **备忘录memo**：存储的计算值，避免将来不必要的重复计算。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "906c1236",
   "metadata": {},
   "source": [
    "## 练习"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "id": "1e3c12ec",
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Exception reporting mode: Verbose\n"
     ]
    }
   ],
   "source": [
    "# 这个单元格让Jupyter在出现运行时故障时提供更多调试信息。\n",
    "# 在进行练习前先运行本单元格。\n",
    "\n",
    "%xmode Verbose"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "170f1deb",
   "metadata": {},
   "source": [
    "### 询问虚拟助手\n",
    "\n",
    "在本章，我提到字典中的键必须是可哈希的，也做出了简短的解释。如果你想要了解更多信息，询问虚拟助手，“Python字典的键为什么必须是可哈希的？”\n",
    "\n",
    "在介绍`in`运算符的章节，我们将单词列表存储为字典的键，以便高效使用`in`运算符。我们可以使用`set`做相同的事，它是另一种Python的内建数据类型。询问虚拟助手，“我怎么从字符串列表创建Python集合，然后检查某个字符串是否是集合的元素？”"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "badf7d65",
   "metadata": {},
   "source": [
    "### 练习\n",
    "\n",
    "字典的`get`方法接受一个键和一个默认值。如果键在字典中，`get`返回对应的值；否则它将返回默认值。例如，以下是一个映射字母和出现次数的字典。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "id": "06e437d9",
   "metadata": {},
   "outputs": [],
   "source": [
    "counter = value_counts('brontosaurus')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c3f6458d",
   "metadata": {},
   "source": [
    "如果我们要查找某个字母在单词中出现的次数，`get`返回它出现的次数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "id": "fc328161",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "counter.get('b', 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "49bbff3e",
   "metadata": {},
   "source": [
    "如果我们查找不存在的字母，我们将获得默认值`0`。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "id": "674b6663",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "counter.get('c', 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4ac3210f",
   "metadata": {},
   "source": [
    "使用`get`编写更简洁的`value_counts`函数。你应该能够消除`if`语句。\n",
    "\n",
    "译注：字典的`setdefault`方法可以进一步简化代码，消除索引赋值语句。感兴趣的可自行搜索。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5413af6e",
   "metadata": {},
   "source": [
    "### 练习\n",
    "\n",
    "你能想到的每个字母只出现一次的单词是什么？让我们看看有没有比`unpredictably`更长的单词。\n",
    "\n",
    "编写函数`has_duplicates`，接受一个序列（比如一个列表或者字符串），如果任意元素数量大于1，返回`True`。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9879d9e7",
   "metadata": {
    "tags": []
   },
   "source": [
    "以下是函数的框架，包含文档测试。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "id": "1744d3e9",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "def has_duplicates(t):\n",
    "    \"\"\"检查一个序列中的元素是否重复。\n",
    "    \n",
    "    >>> has_duplicates('banana')\n",
    "    True\n",
    "    >>> has_duplicates('ambidextrously')\n",
    "    False\n",
    "    >>> has_duplicates([1, 2, 2])\n",
    "    True\n",
    "    >>> has_duplicates([1, 2, 3])\n",
    "    False\n",
    "    \"\"\"\n",
    "    return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "id": "061e2903",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 在这解答"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d8c85906",
   "metadata": {
    "tags": []
   },
   "source": [
    "你可以使用`doctest`测试函数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "id": "62dcdf4d",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "from doctest import run_docstring_examples\n",
    "\n",
    "def run_doctests(func):\n",
    "    run_docstring_examples(func, globals(), name=func.__name__)\n",
    "\n",
    "run_doctests(has_duplicates)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ce4df190",
   "metadata": {
    "tags": []
   },
   "source": [
    "你可以使用这个循环找到最长的无重复字母的单词。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "id": "a1143193",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "no_repeats = []\n",
    "\n",
    "for word in word_list:\n",
    "    if len(word) > 12 and not has_duplicates(word):\n",
    "        no_repeats.append(word)\n",
    "        \n",
    "no_repeats"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "afd5f3b6",
   "metadata": {},
   "source": [
    "### 练习\n",
    "\n",
    "编写函数`find_repeats`，接受一个将键映射到出现次数的字典，比如`value_counts`创建的字典。\n",
    "\n",
    "该函数应该遍历字典，返回计数超过1的键的列表。你可以使用以下函数框架。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "id": "9ea333ff",
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_repeats(counter):\n",
    "    \"\"\"创建一个键的列表，这些键的值大于1。\n",
    "\n",
    "    counter: 映射键到计数的字典；\n",
    "\n",
    "    返回值：键的列表。\n",
    "    \"\"\"\n",
    "    return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "id": "bbd6d241",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 在这解答"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b9b0cbec",
   "metadata": {
    "tags": []
   },
   "source": [
    "你可以使用以下示例测试代码。首先我们将创建一个映射字母到计数的字典。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "id": "ac983c6f",
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'b': 1, 'a': 3, 'n': 2}"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "counter1 = value_counts('banana')\n",
    "counter1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3aa62942",
   "metadata": {
    "tags": []
   },
   "source": [
    "`find_repeats`的结果应该是`['a', 'n']`。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "id": "214345d8",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "repeats = find_repeats(counter1)\n",
    "repeats"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3eaf77f8",
   "metadata": {
    "tags": []
   },
   "source": [
    "以下是一个数字列表的例子，结果应该是`[1, 2]`。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "id": "10e9d54a",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "counter1 = value_counts([1, 2, 3, 2, 1])\n",
    "repeats = find_repeats(counter1)\n",
    "repeats"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1c700d84",
   "metadata": {},
   "source": [
    "### 练习\n",
    "\n",
    "假设你用`value_counts`分别生成两个不同单词的计数字典。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "id": "c97e2419",
   "metadata": {},
   "outputs": [],
   "source": [
    "counter1 = value_counts('brontosaurus')\n",
    "counter2 = value_counts('apatosaurus')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "deb14c7a",
   "metadata": {},
   "source": [
    "编写函数`add_counters`，接受两个字典，返回新字典，包含两个字典的字母，以及它们在两个单词中出现的总次数。\n",
    "\n",
    "这个问题有多种解法，当你有了有效的方案，考虑询问虚拟助手更多不同的方案。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "id": "6cf70355",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 在这解答"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "id": "6a729a14",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 在这解答"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f88110a9",
   "metadata": {},
   "source": [
    "### 练习\n",
    "\n",
    "一个“连锁”的单词通过交叉选取其中的字母可以组成两个单词。比如，\"schooled\"可以分为\"shoe\"和\"cold\"。\n",
    "\n",
    "要在字符串中交叉选择字母，你可以使用三个部分组成的切片运算符，分别是字母的开始索引，结束索引，间隔步长。\n",
    "\n",
    "在下面的索引中，第1部分是`0`，因此从第1个字母开始切片。第2部分是`None`，表示切片直到字符串结尾。第3部分是`2`，选取索引不断增加2的字母。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "id": "56783358",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'shoe'"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "word = 'schooled'\n",
    "first = word[0:None:2]\n",
    "first"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d432332d",
   "metadata": {},
   "source": [
    "第2部分的`None`可以省略，比如下面的切片，从第2个字母开始，选中索引依次增加2的字母。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "id": "77fa8483",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'cold'"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "second = word[1::2]\n",
    "second"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c8c4e3ba",
   "metadata": {},
   "source": [
    "编写函数`is_interlocking`，接受一个单词，如果可以交叉分解为2个单词则返回`True`。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "id": "e5e1030c",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 在这解答"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2787f786",
   "metadata": {
    "tags": []
   },
   "source": [
    "你可以使用以下循环寻找单词列表中的连锁词。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "id": "e04a5c73",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 在这解答"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ced5aa90",
   "metadata": {},
   "outputs": [],
   "source": [
    "interlocking_words = []\n",
    "\n",
    "for word in word_list:\n",
    "    if is_interlocking(word):\n",
    "        interlocking_words.append(word)\n",
    "\n",
    "interlocking_words"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a7f4edf8",
   "metadata": {
    "tags": []
   },
   "source": [
    "[Think Python: 3rd Edition](https://allendowney.github.io/ThinkPython/index.html)\n",
    "\n",
    "Copyright 2024 [Allen B. Downey](https://allendowney.com)\n",
    "\n",
    "Code license: [MIT License](https://mit-license.org/)\n",
    "\n",
    "Text license: [Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-nc-sa/4.0/)"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Tags",
  "kernelspec": {
   "display_name": "cctbx",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
